package com.iter.devbox.datastructure;

import scala.actors.threadpool.Arrays;

/**
 * 冒泡排序
 * bubble：气泡、冒泡
 * 采用最优的冒泡排序，当循环到某元素后排序就已完成，后面的元素不应该再循环
 * 
 * @author Jimly
 */
public class BubbleSort {
	
	/**最简单的冒泡排序*/
	public static void bubbleSort1 (int[] arry) {
		for (int i=0; i<arry.length; i++) {
			for (int j=i+1; j<arry.length; j++) {
				int temp = arry[j];
				if (arry[i] > arry[j]) {
					arry[j] = arry[i];
					arry[i] = temp;
				}
			}
		}
	}

	public static void bubbleSort2 (int[] arry) {
		for (int i=0; i<arry.length; i++) {
			System.out.println(i);
			//内层循环将最小的元素交换到最前面
			for (int j=arry.length-1; j>i; j--) {
				int temp = arry[j];
				//前一个元素 大于 后一个元素
				if (arry[j-1] > arry[j]) {
					//交换两个元素
					arry[j] = arry[j-1];
					arry[j-1] = temp;
				}
			}
		}
	}
	
	public static void bubbleSort3 (int[] arry) {
		boolean flag = true;//true表示没有排序完成，false表示已经排序完成
		for (int i=0; i<arry.length && flag; i++) {
			System.out.println(i);
			flag = false;
			for (int j=arry.length-1; j>i; j--) {
				int temp = arry[j];
				if (arry[j-1] > arry[j]) {
					arry[j] = arry[j-1];
					arry[j-1] = temp;
					flag = true;
				}
			}
		}
	}

	public static void main(String[] args) {
		int[] arry = {0,1,5,9,2,4,3,7,6,8};
		//bubbleSort1(arry);
		//System.out.println(Arrays.toString(arry));
		//bubbleSort2(arry);
		//System.out.println(Arrays.toString(arry));
		bubbleSort3(arry);
		System.out.println(Arrays.toString(arry));
	}
}